package day_2022_4_to_7.day48;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 求数组中出现次数超过一半的数字
 * @author haomin
 * @date 2022/04/20 11:17
 **/
public class Day3_2_MoreThanHalfNum {
    // 方法一：排序数组后该大于数组一半的数必在数组中间位置
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0){
            return 0 ;
        }
        int half = array.length >> 1;
        Arrays.sort(array);
        int target = array[half];
        int count = 0;
        for(int i = 0; i < array.length;i++){
            if(array[i] == target){
                count ++;
            }
        }
        return count > half ? target : 0;
    }

    // 方法二：利用Map的键值对
    public int MoreThanHalfNum_Solution2(int [] array) {
        if(array == null || array.length == 0){
            return 0 ;
        }
        int half = array.length >> 1;
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < array.length;i++){
            if(!map.containsKey(array[i])){
                map.put(array[i],1);
            }else{
                map.replace(array[i],map.get(array[i])+1);
            }
            if(map.get(array[i]) > half){
                return array[i];
            }
        }
        return 0 ;
    }

    // 方法三：
    public int MoreThanHalfNum_Solution3(int [] array) {
        if(array == null && array.length == 0){
            return 0;
        }
        int half = array.length >> 1;
        int target = array[0];
        int times = 1;
        for(int i = 1; i < array.length;i++){
            if(times == 0){
                target = array[i];
                times = 1;
            }else{
                if(target == array[i]){
                    times ++;
                }else{
                    times --;
                }
            }
        }
        times = 0;
        for(int i = 0;i < array.length;i++){
            if(target == array[i]){
                times++;
            }
        }
        return times > half ? target : 0;
    }
}